1. Field of the Invention
This invention relates to memory management, and more specifically to apparatus and methods for compacting regions in memory.
2. Background of the Invention
Any memory management system that does not move objects may be affected by memory fragmentation. One important mechanism for resolving fragmentation is compaction. In an article entitled “An Efficient Parallel Heap Compaction Algorithm,” published in 2004, the authors (Abuaiadh et al.) disclosed, at the time, a state of the art compactor that is currently used in many Java Virtual Machines. The compactor (hereinafter the “Aduaiadh compactor”) parallelizes very well, but requires two passes over the heap, both of which write to the heap. The first pass moves objects and the second pass fixes up references between objects, based on their new locations.
More recently, in an article entitled “The Compressor: Concurrent, Incremental, and Parallel Compaction,” published in 2006, the authors (Kermany et al.) described a novel compactor which improves on the Abuaiadh compactor. The compactor (hereinafter the “Kermany compactor”) is a “stop-the-world” compactor that divides compaction into two phases, referred to herein as the “planning” phase and “move” phase. During the planning phase, the new location of each object or group of objects is determined and recorded in a concise manner in an offset table. Planning is based only on the mark vector—it does not require a pass to read or write to the heap. Once planning is complete, the data in the mark vector and offset table may be combined to determine the destination of any object. This allows the move phase to move objects to their predetermined destinations and fix up their references to other objects at the same time. The move phase is the only phase of the compactor which reads or writes to the heap—planning and external fix-up do not need to read or write to heap memory. The Kermany compactor also includes a concurrent and incremental aspect, which are not discussed here.
Although the Kermany compactor parallelizes the move phase, the parallelization of movement relies on the use of memory mapping, using the operating system's virtual memory subsystem, to ensure that a compactor thread never copies over objects which haven't been copied yet. To accomplish this, the Kermany compactor allocates a second block of memory addresses which map onto the same physical memory as the object heap. As the Kermany compactor compacts the heap, it allocates new “to-virtual-space” pages in which to move objects. As “from-virtual-space” pages are completely evacuated, they are unmapped. Using this technique, the Kermany compactor does not need to worry about moving an object into a page which has not yet been fully evacuated.
However, the Kermany compactor's heavy use of virtual memory for mapping and unmapping is expensive. It typically requires system calls and can be prohibitively slow. It also requires additional address space. The authors acknowledge that this requirement “may create some problem for large heaps on a 32-bit machine.” Also, the Kermany compactor relies on the use of relatively small pages so that virtual memory can be managed at a fine granularity. Hardware and software systems are increasingly moving towards larger page sizes. On large 64-bit systems, for example, 16 GB pages are now available. Such large pages make this mapping/unmapping strategy impractical.
In view of the foregoing, what are needed are apparatus and methods to parallelize object movement in a single pass over an object heap. Ideally, such apparatus and methods will provide mechanisms to ensure that live objects are not overwritten by other live objects, without requiring use of virtual memory.